package com.zhugang.week09;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @program algorithms
 * @description: findLadders
 * @author: chanzhugang
 * @create: 2022/08/23 22:28
 */
public class FindLadders {

    /**
     * 面试题 17.22 单词转换
     * 从一个顶点找到另一个顶点的路径，图上的DFS
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */

    private Set<String> visited = new HashSet<>();
    private List<String> resultPath = new ArrayList<>();
    private boolean found;

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        // 每次只能改变一个字符，且改变的新词在wordList中存在
        // 画出可能的路径，从而看出也是一个图(比较隐式)，抽象成图上的DFS
        dfs(beginWord, endWord, new ArrayList<>(), wordList);
        return resultPath;
    }

    private void dfs(String curWord, String endWord, List<String> path, List<String> wordList) {
        if (found) {
            return;
        }
        path.add(curWord);
        visited.add(curWord);
        if (curWord.equals(endWord)) {
            // 可行解
            resultPath.addAll(path);
            found = true;
            return;
        }

        for (int i = 0; i < wordList.size(); i++) {
            String nextWord = wordList.get(i);
            if (!visited.contains(nextWord) && isValidChange(curWord, nextWord)) {
                dfs(nextWord, endWord, path, wordList);
            }
        }
        // 最末尾删掉
        path.remove(path.size() - 1);
    }

    /**
     * 单词是否只改变了1个字符
     *
     * @param word1
     * @param word2
     * @return
     */
    private boolean isValidChange(String word1, String word2) {
        int diff = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}